package com.ywk.base.dataStructure.stack;

import java.util.Scanner;

/**
 * 计算器
 */
public class Calculator {

	public static void main(String[] args) {
		String str=new String();
		Scanner input=new Scanner(System.in);
//		int a=2;
//		System.out.println(a+=2*10);
		System.out.println("请正确输入要进行计算的数和运算符：");
		str=input.next();
		char[] s=str.toCharArray();
		DouLinkedListStack dlsv=new DouLinkedListStack();//存放运算数的数栈
		DouLinkedListStack dlso=new DouLinkedListStack();//存放运算符的符号栈
		//当连续的两个及以上字符都是运算数，通过计数判断，取出之前压入栈中的值，
		//通过运算将两位数及以上的数重新压入栈中
		int count=0;
		for (int i = 0; i < s.length; i++) {
			count++;
			if(dlsv.isOper(String.valueOf(s[i]))){
				Node o=new Node();
				o.setOper(String.valueOf(s[i]));
				count=0;//当遍历的字符是运算符时，重置count值，当遍历的是两位及以上的数时，通过加1然后处理取出该多位数
				if(!dlso.isEmpty()) {
					//此时扫描的运算符若优先级小于或等于栈顶的运算符，进行运算，从数栈中
					//pop出两个值,再从符号栈中pop出一个运算符
					if(dlso.priority(o.getOper())<=dlso.priority(dlso.topOper())) {
						int num1=dlsv.pop().getValue();
						int num2=dlsv.pop().getValue();
						String oper=dlso.pop().getOper();
						int result=dlsv.calculate(num1, num2, oper);
						Node rn=new Node();
						rn.setValue(result);
						dlsv.push(rn);
						i--;
					}else {//若扫描的运算符优先级大于栈顶的运算符，直接入栈
						dlso.push(o);
					}
				}else {//运算符栈空，扫描的字符直接入栈
					dlso.push(o);
				}
			}else if(!dlsv.isOper(String.valueOf(s[i]))) {
				int value=Integer.parseInt(String.valueOf(s[i]));
				//如果是两位数及以上的数值运算
				if(count>=2) {
					//先取出数栈中栈顶的数乘10加上此时遍历的字符值，然后再入栈
					int num=dlsv.pop().getValue();
					value+=num*10;
				}
				Node n=new Node();
				n.setValue(value);
				dlsv.push(n);
				//判断是否为最后一个字符
				if(i==s.length-1) {
					while(true) {
						if(dlso.head.next==null) {//当符号栈中为空，此时数栈中只有一个结点，该节点的值就是最后的运算结果
							System.out.println(dlsv.head.next.getValue());
							break;
						}else {//符号栈中不为空
							int num1=dlsv.pop().getValue();
							int num2=dlsv.pop().getValue();
							String oper=dlso.pop().getOper();
							int result=dlsv.calculate(num1, num2, oper);
							Node rn=new Node();
							rn.setValue(result);
							dlsv.push(rn);
						}
						
					}
				}
			}
		}
	}
	
}


class DouLinkedListStack{
	public Node head=new Node();
	private Node top=head;
	
	public void push(Node n) {
		top.next=n;
		n.pre=top;
		top=top.next;
	}
	
	public Node pop() {
		Node n=top;
		top=top.pre;
		top.next=null;
		return n;
	}
	
	//判断运算符栈中是否为空
	public boolean isEmpty() {
		return head.next==null?true:false;
	}
	
	//查看栈顶的运算符的值
	public String topOper() {
		return top.getOper();
	}
	
	//返回值越大，运算的优先级越高
	public int priority(String oper) {
		if(oper.equals("+")||oper.equals("-")) {
			return 1;
		}else if(oper.equals("*")||oper.equals("/")) {
			return 2;
		}else {
			return -1;//非法运算符
		}
	}
	//判断是否为运算符
	public boolean isOper(String oper) {
		if(oper.equals("+")||oper.equals("-")||oper.equals("*")||oper.equals("/")) {
			return true;
		}
		return false;
	}
	
	//基本运算
	public int calculate(int num1,int num2,String oper) {
		int result=0;
		switch (oper) {
		case "+":
			result=num1+num2;
			break;
		case "-":
			result=num2-num1;
			break;
		case "*":
			result=num1*num2;
			break;
		case "/":
			result=num2/num1;
			break;
		default:
			break;
		}
		return result;
	}
	
	
	
	
}

class Node{
	private int value;//用于保存运算数值
	private String oper;//用于保存运算符
	public Node next;
	public Node pre;
	
	public Node() {}
	
	public Node(int value) {
		super();
		this.value = value;
	}

	public int getValue() {
		return value;
	}

	public void setValue(int value) {
		this.value = value;
	}

	public String getOper() {
		return oper;
	}

	public void setOper(String oper) {
		this.oper = oper;
	}
}

























